package com.atguigu.tree;

public class BinaryTreeDemo {

	public static void main(String[] args) {
		//ҪһŶ
		BinaryTree binaryTree = new BinaryTree();
		//ҪĽ
		HeroNode root = new HeroNode(1, "ν");
		HeroNode node2 = new HeroNode(2, "");
		HeroNode node3 = new HeroNode(3, "¬");
		HeroNode node4 = new HeroNode(4, "ֳ");
		HeroNode node5 = new HeroNode(5, "ʤ");
		
		//˵ֶöѧϰݹķʽ
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);
		
		//
//		System.out.println("ǰ"); // 1,2,3,5,4
//		binaryTree.preOrder();
		
		// 
//		System.out.println("");
//		binaryTree.infixOrder(); // 2,1,5,3,4
//		
//		System.out.println("");
//		binaryTree.postOrder(); // 2,5,4,3,1
		
		//ǰ
		//ǰĴ 4 
//		System.out.println("ǰʽ~~~");
//		HeroNode resNode = binaryTree.preOrderSearch(5);
//		if (resNode != null) {
//			System.out.printf("ҵˣϢΪ no=%d name=%s", resNode.getNo(), resNode.getName());
//		} else {
//			System.out.printf("ûҵ no = %d Ӣ", 5);
//		}
		
		//
		//3
//		System.out.println("ʽ~~~");
//		HeroNode resNode = binaryTree.infixOrderSearch(5);
//		if (resNode != null) {
//			System.out.printf("ҵˣϢΪ no=%d name=%s", resNode.getNo(), resNode.getName());
//		} else {
//			System.out.printf("ûҵ no = %d Ӣ", 5);
//		}
		
		//
		//ҵĴ  2
//		System.out.println("ʽ~~~");
//		HeroNode resNode = binaryTree.postOrderSearch(5);
//		if (resNode != null) {
//			System.out.printf("ҵˣϢΪ no=%d name=%s", resNode.getNo(), resNode.getName());
//		} else {
//			System.out.printf("ûҵ no = %d Ӣ", 5);
//		}
		
		//һɾ
		
		System.out.println("ɾǰ,ǰ");
		binaryTree.preOrder(); //  1,2,3,5,4
		binaryTree.delNode(5);
		//binaryTree.delNode(3);
		System.out.println("ɾǰ");
		binaryTree.preOrder(); // 1,2,3,4
		
		
		
	}

}

//BinaryTree 
class BinaryTree {
	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}
	
	//ɾ
	public void delNode(int no) {
		if(root != null) {
			//ֻһroot, жrootǲǾҪɾ
			if(root.getNo() == no) {
				root = null;
			} else {
				//ݹɾ
				root.delNode(no);
			}
		}else{
			System.out.println("ɾ~");
		}
	}
	//ǰ
	public void preOrder() {
		if(this.root != null) {
			this.root.preOrder();
		}else {
			System.out.println("Ϊգ޷");
		}
	}
	
	//
	public void infixOrder() {
		if(this.root != null) {
			this.root.infixOrder();
		}else {
			System.out.println("Ϊգ޷");
		}
	}
	//
	public void postOrder() {
		if(this.root != null) {
			this.root.postOrder();
		}else {
			System.out.println("Ϊգ޷");
		}
	}
	
	//ǰ
	public HeroNode preOrderSearch(int no) {
		if(root != null) {
			return root.preOrderSearch(no);
		} else {
			return null;
		}
	}
	//
	public HeroNode infixOrderSearch(int no) {
		if(root != null) {
			return root.infixOrderSearch(no);
		}else {
			return null;
		}
	}
	//
	public HeroNode postOrderSearch(int no) {
		if(root != null) {
			return this.root.postOrderSearch(no);
		}else {
			return null;
		}
	}
}

//ȴHeroNode 
class HeroNode {
	private int no;
	private String name;
	private HeroNode left; //Ĭnull
	private HeroNode right; //Ĭnull
	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft() {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight() {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + "]";
	}
	
	//ݹɾ
	//1.ɾĽڵҶӽڵ㣬ɾýڵ
	//2.ɾĽڵǷҶӽڵ㣬ɾ
	public void delNode(int no) {
		
		//˼·
		/*
		 * 	1. ΪǵĶǵģжϵǰӽǷҪɾ㣬ȥжϵǰǲҪɾ.
			2. ǰӽ㲻Ϊգӽ Ҫɾ㣬ͽthis.left = null; Ҿͷ(ݹɾ)
			3. ǰӽ㲻Ϊգӽ Ҫɾ㣬ͽthis.right= null ;Ҿͷ(ݹɾ)
			4. 2͵3ûɾ㣬ôǾҪеݹɾ
			5.  4Ҳûɾ㣬Ӧеݹɾ.

		 */
		//2. ǰӽ㲻Ϊգӽ Ҫɾ㣬ͽthis.left = null; Ҿͷ(ݹɾ)
		if(this.left != null && this.left.no == no) {
			this.left = null;
			return;
		}
		//3.ǰӽ㲻Ϊգӽ Ҫɾ㣬ͽthis.right= null ;Ҿͷ(ݹɾ)
		if(this.right != null && this.right.no == no) {
			this.right = null;
			return;
		}
		//4.ǾҪеݹɾ
		if(this.left != null) {
			this.left.delNode(no);
		}
		//5.Ӧеݹɾ
		if(this.right != null) {
			this.right.delNode(no);
		}
	}
	
	//дǰķ
	public void preOrder() {
		System.out.println(this); //
		//ݹǰ
		if(this.left != null) {
			this.left.preOrder();
		}
		//ݹǰ
		if(this.right != null) {
			this.right.preOrder();
		}
	}
	//
	public void infixOrder() {
		
		//ݹ
		if(this.left != null) {
			this.left.infixOrder();
		}
		//
		System.out.println(this);
		//ݹ
		if(this.right != null) {
			this.right.infixOrder();
		}
	}
	//
	public void postOrder() {
		if(this.left != null) {
			this.left.postOrder();
		}
		if(this.right != null) {
			this.right.postOrder();
		}
		System.out.println(this);
	}
	
	//ǰ
	/**
	 * 
	 * @param no no
	 * @return ҵͷظNode ,ûҵ null
	 */
	public HeroNode preOrderSearch(int no) {
		System.out.println("ǰ");
		//Ƚϵǰǲ
		if(this.no == no) {
			return this;
		}
		//1.жϵǰӽڵǷΪգΪգݹǰ
		//2.ݹǰңҵ㣬򷵻
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.preOrderSearch(no);
		}
		if(resNode != null) {//˵ҵ
			return resNode;
		}
		//1.ݹǰңҵ㣬򷵻أжϣ
		//2.ǰĽӽڵǷΪգգҵݹǰ
		if(this.right != null) {
			resNode = this.right.preOrderSearch(no);
		}
		return resNode;
	}
	
	//
	public HeroNode infixOrderSearch(int no) {
		//жϵǰӽڵǷΪգΪգݹ
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.infixOrderSearch(no);
		}
		if(resNode != null) {
			return resNode;
		}
		System.out.println("");
		//ҵ򷵻أûҵͺ͵ǰȽϣ򷵻صǰ
		if(this.no == no) {
			return this;
		}
		//ҵݹ
		if(this.right != null) {
			resNode = this.right.infixOrderSearch(no);
		}
		return resNode;
		
	}
	
	//
	public HeroNode postOrderSearch(int no) {
		
		//жϵǰӽڵǷΪգΪգݹ
		HeroNode resNode = null;
		if(this.left != null) {
			resNode = this.left.postOrderSearch(no);
		}
		if(resNode != null) {//˵ҵ
			return resNode;
		}
		
		//ûҵݹк
		if(this.right != null) {
			resNode = this.right.postOrderSearch(no);
		}
		if(resNode != null) {
			return resNode;
		}
		System.out.println("");
		//ûҵͱȽϵǰǲ
		if(this.no == no) {
			return this;
		}
		return resNode;
	}
	
}

//


